package com.formula.datastructure.exercise.graph.undirect;

import com.formula.datastructure.standard.queue.Queue;

/**
 * 方法
 * create
 * insert Vertex
 * delete Vertex
 * insert edge
 * delete edge
 * DFSTraverse 深度遍历
 * BFSTraverse 广度遍历
 */
public class MatrixGraph {

    private static final int INF = 99999;

    int range;

    public int size = 0;

    // 邻接矩阵的边就是一个二维数组
    public int[][] edges;

    // 节点只需要一维数组
    public MatrixVertex[] vertex;
    int[] visit;

    public MatrixGraph() {
        range = 20;
        edges = new int[range][range];
        vertex = new MatrixVertex[range];
        visit = new int[range];
        for (int i = 0; i < range; i++) {
            vertex[i] = new MatrixVertex();
            for (int j = 0; j < range; j++) {
                if (i != j) {
                    edges[i][j] = INF;
                }
            }
        }
    }

    public MatrixGraph(int range) {
        this.range = range;
        edges = new int[range][range];
        vertex = new MatrixVertex[range];
        visit = new int[range];
        for (int i = 0; i < range; i++) {
            vertex[i] = new MatrixVertex();
            for (int j = 0; j < range; j++) {
                if (i != j) {
                    edges[i][j] = INF;
                }
            }
        }
    }

    public void insertVex(String data) {
        vertex[size++].data = data;
    }

    public void insertEdge(int from, int to, int weight) {
        edges[from][to] = weight;
        edges[to][from] = weight;
    }

    /**
     * @param idx 从哪个顶点开始
     */
    public void DFSTraverse(int idx) {
        visit[idx] = 1;
        visit(vertex[idx]);
        for (int i = 0; i < range; i++) {
            //
            if (i != idx && edges[idx][i] > 0 && visit[i] == 0) {
                DFSTraverse(i);
            }
        }
    }

    public void BFSTraverse(int idx) {
        Queue queue = new Queue();
        queue.enQueue(idx);
        while (!queue.isEmpty()) {
            int index = (int) queue.deQueue();
            for (int i = 0; i < range; i++) {
                if (i != index && edges[index][i] > 0) {
                    queue.enQueue(i);
                }
            }
        }
    }

    private void visit(MatrixVertex vertex) {
        System.out.println(vertex.data);
    }

    public static void main(String[] args) {

    }
}
